const ll inf = 1e18;
void solve()
{
  int n, m;
  cin >> n >> m;
  vector<vector<pii>> g(n + 1);
  rep(i, 1, m) {
    int u, v, w;
    cin >> u >> v >> w;
    g[u].pb({v, w});
    g[v].pb({u, w});
  }

  priority_queue<pli, vector<pli>, greater<pli>> Q;

  vl dis(n + 1, inf);
  vi vis(n + 1), pre(n + 1);
  dis[0] = dis[1] = 0;
  Q.push({0, 1});

  while (!Q.empty()) {
    auto [s, v] = Q.top();
    Q.pop();

    if (vis[v]) {
      continue;
    }
    vis[v] = true;
    for (auto &[u, w]: g[v]) {
      if (dis[u] > s + w) {
        pre[u] = v;
        dis[u] = s + w;
        Q.push({dis[u], u});
      }
    }
  }

  ll ans1 = dis[n], ans2 = inf, ret = 0;
  int j = n, lst = n + 1;
  while (j) {
    for (auto &[v, w] : g[j]) {
      if (v != lst && v != pre[j]) {
        ans2 = min(ans2, dis[v] + w + ret);
      }
    }
    ret += dis[j] - dis[pre[j]];
    lst = j;
    j = pre[j];
  }
  if (ans1 == inf || ans2 == inf) {
    cout << -1;
  } else {
    cout << ans1 + ans2 << '\n';
  }
}